#include <stdio.h>
#include "ljjz.h"

#define  MAXNUM 32767                            

void  ShorttestPath_Dijkstra(AdjMatrix G, int v);
int main() {
	AdjMatrix a;
	int n = 0;
	int e = 0;
	int v = 0;
	printf_s("请输入图的顶点数：");
	scanf_s("%d", &n);
	printf_s("请输入图的边数：");
	scanf_s("%d", &e);
	creat(&a, n, e);
	printf_s("请输入初始顶点：");
	scanf_s("%d", &v);
	ShorttestPath_Dijkstra(a, v);
	return 0;
}


void  ShorttestPath_Dijkstra(AdjMatrix G, int v)
{
	float dist[MAXNUM];
	int s[MAXNUM], path[MAXNUM];
	int i, j, u, w, min;
	int count = 0;
	for (int i = 0; i < G.numV; i++)
	{
		dist[i] = G.Edge[v][i]; s[i] = 0;
		if (i != v && dist[i] < MAXNUM)  path[i] = v;
		else path[i] = -1;
	}
	s[v] = 1; dist[v] = 0;
	for (i = 0; i < G.numV; i++)
	{
		min = MAXNUM;
		for (j = 0; j < G.numV; j++)
			if (s[j] != 1 && dist[j] < min)
			{
				min = dist[j];  u = j;
			}
		s[u] = 1;
		for (w = 0; w < G.numV; w++)
			if (s[w] == 0)
				if (dist[w] > dist[u] + G.Edge[u][w])
				{
					dist[w] = dist[u] + G.Edge[u][w]; path[w] = u;
				}
	}
	for (int i = 0; i < G.numV; i++) {
		count += dist[i];
	}
	printf_s("从%d开始的最短路径为%d\n", v, count);
}
